// https://www.lintcode.com/problem/kill-process/

public class Solution {
    /**
     * @param pid: the process id
     * @param ppid: the parent process id
     * @param kill: a PID you want to kill
     * @return: a list of PIDs of processes that will be killed in the end
     */
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        // Write your code here
        List<Integer> ret = new ArrayList<>();
        List<Integer> kills = new ArrayList<>();
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < pid.size(); ++i) {
            if (!map.containsKey(ppid.get(i))) {
                map.put(ppid.get(i), new ArrayList<>());
            }
            map.get(ppid.get(i)).add(pid.get(i));
        }
        kills.add(kill);
        while (kills.size() > 0) {
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < kills.size(); ++i) {
                int kid = kills.get(i);
                ret.add(kid);
                if (map.containsKey(kid)) {
                    List<Integer> new_kills = map.get(kid);
                    for (int j = 0; j < new_kills.size(); ++j) {
                        tmp.add(new_kills.get(j));
                    }
                }
            }
            kills = tmp;
        }
        return ret;
    }
}